package top.datacluster.basic.algorithm.leetcode.stack;

import java.util.LinkedList;

public class LeetCodeView60 {

    private LinkedList<Integer> queue = new LinkedList<>();

    public int trap(int[] height) {
        int result = 0;
        queue.offerLast(height[0]);
        for (int i = 1; i < height.length; i++){
            if (height[i] >= queue.peekFirst()){
                int temp = queue.pollFirst();
                if (temp != 0){
                    while (!queue.isEmpty()){
                        result += temp - queue.pollFirst();
                    }
                }
                queue.offerLast(height[i]);
            }else{
                queue.offerLast(height[i]);
            }
        }
        if (queue.size() > 2){
            int min = queue.pollLast();
            while (!queue.isEmpty()){
                if (queue.peekLast() >= min){
                    min = queue.pollLast();
                }else{
                    result += min - queue.pollLast();
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] test = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(new LeetCodeView60().trap(test));
    }
}
